
#include <stddef.h>
#include <string.h>

#include "MemPort.h"

typedef unsigned int Memory_T;

Memory_T *memBase;
Memory_T memSize;
Memory_T avail;  //1st index of the 1st free range

#define GetSize(x)	memBase[x]
#define GetLink(x)	memBase[(x)+1]
#define SetSize(x, s)	do{memBase[x] = (s);}while(0)
#define SetLink(x, v)	do{memBase[(x)+1] = (v);}while(0)

#if 0
int mem_check(void) {
	Memory_T next = avail;
	while (next != memSize) {
		if (next >= GetLink(next)) {
			return 0;
		}
		next = GetLink(next);
	}
	return 1;
}

int mem_allAvail(void) {
	if (avail != 0){
		return 1;
	}
	if (GetSize(avail) != memSize) {
		return 2;
	}
	return 0;
}
#endif 

static void do_init(void* ptr, unsigned size) {
	avail = 0;
	memBase = (Memory_T *)ptr;
	memSize = size / sizeof(Memory_T);
	SetSize(avail, memSize);
	SetLink(avail, memSize);
}

static void* do_alloc(unsigned n) {
	Memory_T current, previous, remain;

	n++; //增加保存分配块大小的空间
	for (current = previous = avail; current != memSize; current = GetLink(current)) { //查找连续空间满足的块
		if (GetSize(current) >= n) {
			break;
		}
		previous = current;
	}

	if (current == memSize) {//没有找到满足条件的块
		return NULL;
	}

	remain = GetSize(current) - n;
	if (remain < 2) { //没有足够的空间存储Link和Size，整块分配
		if (current == avail) { //首块即匹配
			avail = GetLink(current);
		}
		else {// 删除分配的块
			SetLink(previous, GetLink(current));
		}
		remain = 0;
	}
	else {
		SetSize(current, remain); // 设置被分配块的大小为剩余的大小
		SetSize(current + remain, n); //从块的末尾分配空间
	}
	return (void*)&memBase[current + remain + 1]; //返回Size后面的地址
}

static void do_free(Memory_T* f, unsigned n) {
	Memory_T current, previous, toFree;

	toFree = f - memBase;
	if (toFree < avail) { //释放的块在avail之前
		if (((toFree + n) == avail) && avail < memSize) { //被释放的块与其后的自由块连续
			SetSize(toFree, n + GetSize(avail)); //合并 toFree与avail
			SetLink(toFree, GetLink(avail));
		}
		else{
			SetLink(toFree, avail); 
		}
		avail = toFree;
	}
	else {
		current = previous = avail;
		while ((toFree > current) && (current != memSize)){ //查找被释放块的前、后自由块
			previous = current;
			current = GetLink(previous);
		}

		if (((toFree + n) == current) && current != memSize) {//toFree与其后的自由块连续
			n += GetSize(current);	//合并toFree 与其后的自由块
			SetLink(toFree, GetLink(current));
		}
		else{
			SetLink(toFree, current);
		}

		if ((previous + GetSize(previous)) == toFree) { //toFree与其前的自由块连续
			SetSize(previous, GetSize(previous) + n); //合并toFree 与 其前的自由块
			SetLink(previous, GetLink(toFree));
		}
		else {
			SetSize(toFree, n);
			SetLink(previous, toFree);
		}
	}
}

void mem_init(void*p, unsigned size) {
	if (p) {
		do_init(p, size);
	}
}

void* mem_alloc(unsigned n) {
	Memory_T num;
	void* p;
	
	if (n == 0) {
		return NULL;
	}
	n += sizeof(Memory_T) - 1; //计算对齐大小
	num = n / sizeof(Memory_T); 
	MEM_ENTER_CRITICEL();
	p = do_alloc(num);
	MEM_EXIT_CRITICEL();
	return p;
}

void mem_free(void* f) {
	if (f) {
		Memory_T* p = (Memory_T*)f - 1;
		
		MEM_ENTER_CRITICEL();
		do_free(p, *p);
		MEM_EXIT_CRITICEL();
	}
}


#if 0
void* mem_realloc(void* p, unsigned n) {
	if (p) {
		Memory_T* b = (Memory_T*)p - 1;
		unsigned size = (*b - 1) * sizeof(Memory_T);
		Memory_T* newPtr;

		if (size >= n) {
			return p;
		}
		newPtr = (Memory_T*)mem_alloc(n);
		if (newPtr) {
			memcpy(newPtr, p, size);
			mem_free(p);
		}
		return (void*)newPtr;
	}
	return mem_alloc(n);
}
#endif 

#if 0
void* mem_calloc(unsigned number, unsigned size) {
	unsigned total = number*size;
	void* p = mem_alloc(total);
	if (p) {
		memset(p, 0, total);
	}
	return p;
}
#endif 

#if 0
void* mem_resize(void* p, unsigned n) {
	if (p) {
		Memory_T* b = (Memory_T*)p - 1;
		Memory_T space = *b - 1; //减去size所占的空间
		Memory_T num;
		Memory_T remain;

		num = n + sizeof(Memory_T) - 1;
		num /= sizeof(Memory_T);
		if (space < num) {
			mem_free(p);
			return mem_alloc(n);
		}
		remain = space - num;
		if (remain > 2) {
			Memory_T* f = (Memory_T*)p + num;
			*b = num + 1;
			*f = remain;
			mem_free(f + 1);
		}
		return p;
	}
	return mem_alloc(n);
}
#endif
